package leetcode;

/**
 * 完全背包问题：组合总和2
 */
public class Solution49 {
    class Solution {
        public int combinationSum4(int[] nums, int target) {
            if(nums == null || nums.length == 0){
                return 0;
            }
            //定义dp数组
            int[] dp = new int[target + 1];
            //初始化dp数组
            dp[0] = 1;
            //先遍历背包后遍历物品
            for(int j = 0;j <= target;j++){
                for(int i = 0;i < nums.length;i++){
                    if(j >= nums[i]){  //背包大于物品
                        dp[j] = dp[j] + dp[j - nums[i]];
                    }
                }
            }
            return dp[target];
        }
    }
}
